B.TECH - Semester 7 design and analysis of algorithms Question Paper 2020 (sep)
Practice authentic previous year university questions for better exam preparation.
- Define Red-Black trees. Give an example.
- Define strongly connected components of a graph. Give an example.
- Can the spanning tree of a graph be unique? Explain.
- Analyze the running time of Strassen's matrix multiplication algorithm.
- Write an algorithm to perform BFS on a graph. $$ \text { ( } 10 \times 4=40 \text { Marks) } $$
- (a) Derive the best, worst and average case time complexity of linear search. 14
- (b) Solve $T(n)=4 T(n / 2)+n^{2}$ using master method.
- (a) What do you mean by priority queue? Explain any one application of priority queue.
- (b) Explain randomized version of quick sort. Analyze its running time.
- (a) Write an algorithm to insert a node into an AVL tree.
- (b) Construct a red-black tree by inserting the keys into an initially empty tree $2,1,4,5,9,3,6,7$. Delete 4 and 6 from the constructed tree. OR
- (a) Explain about union and find operations on disjoint sets.
- (b) Find the shortest path from s to the remaining vertices.
- (a) Explain integer multiplication problem. How it can be solved using divide and conquer method?
- (b) Explain mergesort algorithm. Sort the sequence 21, 11, 71, 51, 61, 24, 88, 33 using merge sort
- (a) State the travelling salesman problem. Explain the method to solve it using branch and bound technique.
- (b) Explain :
- (i) NP-Completeness (ii) NP-Hardness.
- Define Big Oh notation. Express $f(n)=2 n+8$ using Big Oh notation.
- Solve $T(n)=2 T(n / 2)+n$ using iteration method.
- Define heap. What are the different types of heaps?
- Obtain the time complexity of Prim's algorithm for finding the minimum spanning tree.
- Derive a recurrence to find the number of ways of parenthesizing a chain of $n$ matrices.
Browse Previous Year Question Papers →